#include <stdio.h>
#include <string.h>
#include <time.h>

// Name: Sudoku | 2018 - 2021
// Version: 1.0
// Last update: 2021.8.15
// ----------------------------------------
// Developer: Monkeyhbd | 2017 - 2021
// Email: monkeyhbd@163.com
// ----------------------------------------
//
//                         ##
//                         ##    ##    ####    ##    ##    ##      ##          ##
//     ##  ##      ####    ##  ##    ##    ##    ##  ##    ##      ##          ##
//   ##  ##  ##  ##    ##  ####      ########      ##      ####    ####      ####
//   ##  ##  ##  ##    ##  ##  ##    ##            ##      ##  ##  ##  ##  ##  ##
//   ##  ##  ##    ####    ##    ##    ####      ##        ##  ##  ####      ####
//
// ----------------------------------------
// License: GNU GPLv2

void gen2sudoku_unit(char gen[10], int sudoku_unit[9][9])
{
    int n;
    for (int idx = 0; idx < 9; idx += 1)
    {
        n = (int) gen[idx] - 48;
        if (n > 0 && n < 10)
        {
            for (int x = 0; x < 9; x += 1)
            {
                sudoku_unit[idx][x] = 0;
            }
            sudoku_unit[idx][n-1] = 1;
        }
        else
        {
            for (int x = 0; x < 9; x += 1)
            {
                sudoku_unit[idx][x] = 1;
            }
        }
    }
}

void test2sudoku_unit(char test[100], int sudoku_unit[9][9]);

int array_read(int array[9])
{
    // {0, 0, 0, 0, 0, 0, 0, 1, 0} --> 8  (1 ~ 9)
    // {0, 0, 0, 0, 1, 1, 0, 1, 0} --> 0
    // {0, 0, 0, 0, 0, 0, 0, 0, 0} --> -1

    int sum_of_1 = 0;
    int idx_of_1;
    for (int idx = 0; idx < 9; idx += 1)
    {
        if (array[idx] == 1)
        {
            sum_of_1 += 1;
            idx_of_1 = idx;
        }
    }

    if (sum_of_1 == 1)
    {
        return idx_of_1 + 1;
    }
    else if (sum_of_1 == 0)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}

int array_count(int array[9])
{
    int sum_of_1 = 0;
    int idx_of_1;
    for (int idx = 0; idx < 9; idx += 1)
    {
        if (array[idx] == 1)
        {
            sum_of_1 += 1;
            idx_of_1 = idx;
        }
    }

    return sum_of_1;
}

void array_clear(int array[9], int n)
{
    for (int idx = 0; idx < 9; idx += 1)
    {
        array[idx] = n;
    }
}

void array_write(int array[9], int num)
{
    array_clear(array, 0);
    array[num-1] = 1;
}

void print_sudoku_unit(int sudoku_unit[9][9])
{
    for (int a = 0; a < 9; a += 1)
    {
        for (int b = 0; b < 9; b += 1)
        {
            printf("%d ", sudoku_unit[a][b]);
        }
        printf("--> %d\n", array_read(sudoku_unit[a]));
    }
}

void print_sudoku_unit_simple(int sudoku_unit[9][9])
{
    for (int a = 0; a < 9; a += 1)
    {
        printf("[%d] ", array_read(sudoku_unit[a]));
    }
    printf("\n");
}

void print_sudoku(int sudoku[9][9][9])
{
    for (int idx = 0; idx < 9; idx += 1)
    {
        print_sudoku_unit_simple(sudoku[idx]);
    }
}

int check_unit(int *sudoku_unit[9])
{
    int counter[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
    int key;

    for (int idx = 0; idx < 9; idx += 1)
    {
        key = array_read(sudoku_unit[idx]);
        if (key > 0)
        {
            counter[key-1] += 1;
        }
    }

    for (int idx = 0; idx < 9; idx += 1)
    {
        if (counter[idx] > 1)
        {
            return 0;
        }
    }

    return 1;
}

int check(int sudoku[9][9][9])
{
    int *current_unit[9];
    for (int y = 0; y < 9; y += 1)
    {
        for (int x = 0; x < 9; x += 1)
        {
            current_unit[x] = sudoku[y][x];
        }
        if (check_unit(current_unit) == 0)
        {
            return 0;
        }
    }

    for (int x = 0; x < 9; x += 1)
    {
        for (int y = 0; y < 9; y += 1)
        {
            current_unit[y] = sudoku[y][x];
        }
        if (check_unit(current_unit) == 0)
        {
            return 0;
        }
    }

    int c;
    for (int b = 0; b < 9; b += 1)
    {
        c = 0;
        for (int y = (b/3)*3; y < (b/3)*3 + 3; y += 1)
        {
            for (int x = (b%3)*3; x < (b%3)*3 + 3; x += 1)
            {
                current_unit[c] = sudoku[y][x];
                c += 1;
            }
        }
        if (check_unit(current_unit) == 0)
        {
            return 0;
        }
    }

    return 1;
}

// Example: [[1],[8],[6],[2],[7],[3,9],[9],[4],[5,9]] --> [[1],[8],[6],[2],[7],[3],[9],[4],[5]]
void exclusion_unit(int *sudoku_unit[9])
{
    int key;
    int sum1, sum2;

    for (;;)
    {
        sum1 = 0;
        for (int idx = 0; idx < 9; idx += 1)
        {
            sum1 += array_count(sudoku_unit[idx]);
        }

        for (int idx = 0; idx < 9; idx += 1)
        {
            key = array_read(sudoku_unit[idx]);
            if (key > 0)
            {
                for (int x = 0; x < 9; x += 1)
                {
                    sudoku_unit[x][key-1] = 0;
                }
                sudoku_unit[idx][key-1] = 1;
            }
        }

        sum2 = 0;
        for (int idx = 0; idx < 9; idx += 1)
        {
            sum2 += array_count(sudoku_unit[idx]);
        }

        if (sum1 == sum2)
        {
            break;
        }
    }
}

// Example: input: [[1],[8],[6],[2],[7],[3,9],[5,9],[4],[5,9]] --> [[1],[8],[6],[2],[7],[3],[5,9],[4],[5,9]]
void look_unit(int *sudoku_unit[9])
{
    int counter[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};

    for (int idx = 0; idx < 9; idx += 1)
    {
        if (array_count(sudoku_unit[idx]) > 1)
        {
            for (int x = 0; x < 9; x += 1)
            {
                counter[x] += sudoku_unit[idx][x];
            }
        }
    }

    for (int x = 0; x < 9; x += 1)
    {
        if (counter[x] == 1)
        {
            for (int idx = 0; idx < 9; idx += 1)
            {
                if (sudoku_unit[idx][x] == 1)
                {
                    array_clear(sudoku_unit[idx], 0);
                    sudoku_unit[idx][x] = 1;
                }
            }
        }
    }
}

void exclusion(int sudoku[9][9][9])
{
    int *current_unit[9];
    int sum1, sum2;

    for (;;)
    {
        sum1 = 0;
        for (int y = 0; y < 9; y += 1)
        {
            for (int x = 0; x < 9; x += 1)
            {
                sum1 += array_count(sudoku[y][x]);
            }
        }

        for (int y = 0; y < 9; y += 1)
        {
            for (int x = 0; x < 9; x += 1)
            {
                current_unit[x] = sudoku[y][x];
            }
            exclusion_unit(current_unit);
            look_unit(current_unit);
        }

        for (int x = 0; x < 9; x += 1)
        {
            for (int y = 0; y < 9; y += 1)
            {
                current_unit[y] = sudoku[y][x];
            }
            exclusion_unit(current_unit);
            look_unit(current_unit);
        }

        int c;
        for (int b = 0; b < 9; b += 1)
        {
            c = 0;
            for (int y = (b/3)*3; y < (b/3)*3 + 3; y += 1)
            {
                for (int x = (b%3)*3; x < (b%3)*3 + 3; x += 1)
                {
                    current_unit[c] = sudoku[y][x];
                    c += 1;
                }
            }
            exclusion_unit(current_unit);
            look_unit(current_unit);
        }

        sum2 = 0;
        for (int y = 0; y < 9; y += 1)
        {
            for (int x = 0; x < 9; x += 1)
            {
                sum2 += array_count(sudoku[y][x]);
            }
        }

        if (sum1 == sum2)
        {
            break;
        }
    }
}

int enumeration_core(int sudoku[9][9][9], int sudoku_backup[9][9][9], int *empty[], int level, int level_max)
{

    int position[2] = {empty[level][0], empty[level][1]};
    int last_return;

    for (int idx = 0; idx < 9; idx += 1)
    {
        if (sudoku_backup [position[1]] [position[0]] [idx] == 1)
        {
            array_clear(sudoku [position[1]] [position[0]], 0);
            sudoku [position[1]] [position[0]] [idx] = 1;
            if (level == level_max)
            {
                if (check(sudoku))
                {
                    return 0;
                }
            }
            else
            {
                if (check(sudoku))
                {
                    last_return = enumeration_core(sudoku, sudoku_backup, empty, level+1, level_max);
                    if (last_return == 0)
                    {
                        return 0;
                    }
                }
            }
        }
    }

    memcpy(sudoku [position[1]] [position[0]], sudoku_backup [position[1]] [position[0]], 9*sizeof(int));

    return -1;
}

void enumeration(int sudoku[9][9][9])
{
    int sum1 = 0;
    for (int y = 0; y < 9; y += 1)
    {
        for (int x = 0; x < 9; x += 1)
        {
            sum1 += array_count(sudoku[y][x]);
        }
    }

    if (sum1 > 81)
    {
        int sudoku_backup[9][9][9];
        memcpy(sudoku_backup, sudoku, 9*9*9*sizeof(int));

        int empty_count = 0;
        for (int y = 0; y < 9; y += 1)
        {
            for (int x = 0; x < 9; x += 1)
            {
                if (array_count(sudoku[y][x]) > 1)
                {
                    empty_count += 1;
                }
            }
        }

        int empty[81][2];
        empty_count = 0;
        for (int y = 0; y < 9; y += 1)
        {
            for (int x = 0; x < 9; x += 1)
            {
                if (array_count(sudoku[y][x]) > 1)
                {
                    empty[empty_count][0] = x;
                    empty[empty_count][1] = y;
                    empty_count += 1;
                }
            }
        }

        int *e[81];
        for (int idx = 0; idx < empty_count; idx += 1)
        {
            e[idx] = empty[idx];
        }

        enumeration_core(sudoku, sudoku_backup, e, 0, empty_count-1);

    }
}


int main()
{
    clock_t t0, te;

    char gen[10];
    int sudoku[9][9][9];

    for (int idx = 0; idx < 9; idx += 1)
    {
        printf("Line%d: ", idx + 1);
        scanf("%s", gen);
        gen2sudoku_unit(gen, sudoku[idx]);
    }

    printf("\n");

    t0 = clock();

    exclusion(sudoku);
    enumeration(sudoku);

    print_sudoku(sudoku);

    te = clock();

    printf("\n");

    printf("The C program use %lf s.\n", (double)(te - t0) / CLOCKS_PER_SEC);

    return 0;
}
